package 完全背包

/*
原题链接:
https://leetcode.cn/problems/combination-sum-iv/description/

377. 组合总和 Ⅳ
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：
输入：nums = [9], target = 3
输出：0

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

思路: 动态规划
一. dp数组含义:
  - dp[i]: 凑成目标正整数为 i的排列数个数为 dp[i]

二. 递推公式
  - dp[i] = min { dp[i]
    { dp[i-nums[i]]

三. 初始化
  - dp[0] = 0   如果要组合的target为0, 那根本没有元素符合, 直接返回0
    其它非零位置需要初始化为0

四. 确定遍历顺序
  - 个数使用次数不限, 属于完全背包.
    [1,2,1]和[1,1,2]属于两种情况, 属于求排列数, 那么需要先遍历背包, 后遍历物品

五. 打印dp数组
*/
func combinationSum4(nums []int, target int) int {

	dp := make([]int, target+1) //定义dp数组
	dp[0] = 1                   // 初始化

	// 遍历顺序, 先遍历背包,再循环遍历物品
	for j := 0; j <= target; j++ {
		for i := 0; i < len(nums); i++ {
			if j >= nums[i] {
				dp[j] += dp[j-nums[i]]
			}
		}
	}

	return dp[target]
}
